<html>
<head><meta charset="utf-8"><title>Optimistic incremental compilation? · t-compiler · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/index.html">t-compiler</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html">Optimistic incremental compilation?</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="210704944"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/210704944" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#210704944">(Sep 21 2020 at 06:22)</a>:</h4>
<p>Hypothetically, if we're doing incremental compilation, and we're not yet sure if the interface file for a given crate is going to be the same since the last compile, if we have spare CPUs, could we optimistically assume that it <em>is</em> the same, start recompiling a dependent crate, and then throw away any compilation that depends on things that ended up changing in the interface file?</p>



<a name="210714355"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/210714355" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#210714355">(Sep 21 2020 at 08:44)</a>:</h4>
<p>I think this is a question for <a class="stream" data-stream-id="246057" href="/#narrow/stream/246057-t-cargo">#t-cargo</a>.</p>



<a name="210714474"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/210714474" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#210714474">(Sep 21 2020 at 08:46)</a>:</h4>
<p>Such a change would involve both rustc and cargo, since the compiler would need to support speculatively starting to build with a potentially stale interface file, and then later cancelling only the builds that rely on things that changed.</p>



<a name="210714733"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/210714733" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#210714733">(Sep 21 2020 at 08:50)</a>:</h4>
<p>I think compilation will need to be aborted on any change to the interface file as rustc uses DefId's which would change when the interface file changes. Incremental compilation uses a DefId &lt;-&gt; DefPath map to remap the DefIds when loading the crate metadata, but once the crate metadata is loaded it only uses DefId's. Aborting rustc is as simple as killing, which cargo can easily do.</p>



<a name="210730292"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/210730292" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> teor <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#210730292">(Sep 21 2020 at 11:53)</a>:</h4>
<p>How does cargo sort dependencies?<br>
Does it compile the dependencies which affect the largest number of crates first?<br>
Or the dependencies with the deepest tree?</p>
<p>The optimal solution varies based on the compile time of each crate, and maybe the number of cores. But both tree size and depth order would be pretty close.</p>



<a name="210730427"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/210730427" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> teor <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#210730427">(Sep 21 2020 at 11:55)</a>:</h4>
<p>Back to your original proposal - rust-analyzer would also benefit from speculative compilation. Most IDE-based edits won't change the interfaces.</p>



<a name="210733387"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/210733387" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> panstromek <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#210733387">(Sep 21 2020 at 12:27)</a>:</h4>
<p><span class="user-mention" data-user-id="325209">@teor</span>  Cargo now just starts from leaf crates and at each step selects the crate that has highest number of transitive dependants. If you look at issues labeled with Performance, there's a number of  ideas for potential  improvements discussed  <a href="https://github.com/rust-lang/cargo/labels/Performance">https://github.com/rust-lang/cargo/labels/Performance</a></p>



<a name="210733482"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/210733482" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> panstromek <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#210733482">(Sep 21 2020 at 12:28)</a>:</h4>
<p>Generally, this problem is called DAG scheduling and it's NP-hard</p>



<a name="210737761"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/210737761" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#210737761">(Sep 21 2020 at 13:06)</a>:</h4>
<p><span class="user-mention silent" data-user-id="325209">teor</span> <a href="#narrow/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F/near/210730427">said</a>:</p>
<blockquote>
<p>Back to your original proposal - rust-analyzer would also benefit from speculative compilation. Most IDE-based edits won't change the interfaces.</p>
</blockquote>
<p>The MIR of functions is in many cases part of the interface. While during check builds only <code>const fn</code> would need to have MIR available for them, for full builds generic and <code>#[inline]</code> functions need to be included in the metadata too.</p>



<a name="210801945"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/210801945" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#210801945">(Sep 21 2020 at 21:23)</a>:</h4>
<p>Is the problem even just NP-hard? In the fully general case, it seems like that problem is "knowing-the-future"-hard. ;)</p>



<a name="210802037"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/210802037" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#210802037">(Sep 21 2020 at 21:24)</a>:</h4>
<p>Depending on how much effort it takes to figure out how long something is going to take, vs actually doing it.</p>



<a name="210802107"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/210802107" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#210802107">(Sep 21 2020 at 21:25)</a>:</h4>
<p>(That does raise one interesting question: perhaps it makes sense to do a quick pass that ingests the code of a crate, and uses that information to decide when to schedule further processing of that crate once we know the size of the problem.)</p>



<a name="210813874"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/210813874" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Joshua Nelson <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#210813874">(Sep 21 2020 at 23:42)</a>:</h4>
<p>Sheer number of lines is not a great metric</p>



<a name="210813918"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/210813918" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Joshua Nelson <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#210813918">(Sep 21 2020 at 23:42)</a>:</h4>
<p>Proof: the recent issue about exponential compile times for async functions</p>



<a name="210815014"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/210815014" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Joshua Nelson <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#210815014">(Sep 21 2020 at 23:59)</a>:</h4>
<p><span class="user-mention silent" data-user-id="239881">Josh Triplett</span> <a href="#narrow/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F/near/210801945">said</a>:</p>
<blockquote>
<p>Is the problem even just NP-hard? In the fully general case, it seems like that problem is "knowing-the-future"-hard. ;)</p>
</blockquote>
<p>could cargo store how long crates took the last time?</p>



<a name="210815036"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/210815036" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Joshua Nelson <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#210815036">(Sep 21 2020 at 23:59)</a>:</h4>
<p>and then guesstimate from there for incremental</p>



<a name="210822874"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/210822874" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> teor <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#210822874">(Sep 22 2020 at 02:30)</a>:</h4>
<p>Profile-guided optimisation, but for parallel compilation scheduling</p>



<a name="210822910"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/210822910" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Joshua Nelson <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#210822910">(Sep 22 2020 at 02:32)</a>:</h4>
<p>basically, yeah</p>



<a name="210833100"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/210833100" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> panstromek <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#210833100">(Sep 22 2020 at 06:48)</a>:</h4>
<p>That's what one of the open issues suggests</p>



<a name="210833122"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/210833122" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> panstromek <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#210833122">(Sep 22 2020 at 06:49)</a>:</h4>
<p>I think the comment on NP-conpleteness is there. I am actually not sure which specific instance of the problem has this property</p>



<a name="210833296"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/210833296" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> panstromek <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#210833296">(Sep 22 2020 at 06:51)</a>:</h4>
<p>I'd think it's the one where you know how long each step is going to take, so speculative one would obviously be even harder</p>



<a name="210833388"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/210833388" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> panstromek <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#210833388">(Sep 22 2020 at 06:53)</a>:</h4>
<p>But not really meaningfully on O(x) scale</p>



<a name="210902459"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/210902459" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> est31 <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#210902459">(Sep 22 2020 at 17:16)</a>:</h4>
<p>Is it fair to call it an interface file at this point?</p>



<a name="210902504"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/210902504" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> est31 <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#210902504">(Sep 22 2020 at 17:17)</a>:</h4>
<p>IIRC it contains the full source code of the crate and all MIR code</p>



<a name="210903106"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/210903106" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> est31 <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#210903106">(Sep 22 2020 at 17:20)</a>:</h4>
<p><span class="user-mention silent" data-user-id="239881">Josh Triplett</span> <a href="#narrow/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F/near/210802107">said</a>:</p>
<blockquote>
<p>(That does raise one interesting question: perhaps it makes sense to do a quick pass that ingests the code of a crate, and uses that information to decide when to schedule further processing of that crate once we know the size of the problem.)</p>
</blockquote>
<p>I agree in believing that there is some potential hidden here <span class="user-mention" data-user-id="239881">@Josh Triplett</span> . See this github comment for my own views on the matter: <a href="https://github.com/rust-lang/cargo/issues/7396#issuecomment-533762594">https://github.com/rust-lang/cargo/issues/7396#issuecomment-533762594</a></p>
<p>A good starting point would be to take the logs of one of the crater runs and then run various heuristics on them comparing compile time with line count, size of the source code, number of functions, how complex types are, etc and finding good correlates. Then use one of those correlates as input for cargo.</p>



<a name="210961550"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/210961550" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#210961550">(Sep 23 2020 at 05:49)</a>:</h4>
<p>Hmm, I wonder if there's a way to train an NN on this.  This kind of "it doesn't matter if it's somewhat wrong sometimes so long as it's usually better than what we could otherwise guess" seems like the kind of place that AI can actually be useful, not just a meme.</p>



<a name="211002937"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/211002937" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> teor <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#211002937">(Sep 23 2020 at 13:33)</a>:</h4>
<p>A heuristic should get you similar results, but have more predictable behaviour (and be easier to maintain, or tune if particular projects have issues)</p>



<a name="211003027"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/211003027" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> teor <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#211003027">(Sep 23 2020 at 13:34)</a>:</h4>
<p>One of the issues with neural networks is that they're effectively an all-or-nothing black box</p>



<a name="211003636"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/211003636" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Joshua Nelson <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#211003636">(Sep 23 2020 at 13:38)</a>:</h4>
<p>I still think PGO is the best way to do this personally</p>



<a name="211003685"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Optimistic%20incremental%20compilation%3F/near/211003685" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Joshua Nelson <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Optimistic.20incremental.20compilation.3F.html#211003685">(Sep 23 2020 at 13:39)</a>:</h4>
<p>If it works well enough cargo could even upload the stats to <a href="http://crates.io">crates.io</a> so that everyone using <code>cargo install</code> benefits too</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>